<!DOCTYPE html>
<html lang="cn">

<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="description" content="字典 现代编程语言，例如Python和Go中都有字典，其作为一种常见数据结构使用频率非常高。一般作为内置类型，解释器或者编译器都会对其特别的照顾，做相当多的优化，它的设计也需要在通用和性能上找到平衡，当然也是我们非常好的学习案例。
要存储一批数据，我们最先想到的就是用数组，因为它对所有的存储器亲和性是最好的，内存可以看成是一个大的字节数组，CPU cache line也是一个64字节的数组。但数组有个问题，即索引效率低，我们往往是通过排序然后进行二分查找来提高索引的效率。可是如果我们的数据需要频繁的编辑(插入、删除、修改)时，这种排序就可能造成我们需要频繁的对其中的局部进行重排，这时候延伸出了大小堆、树堆等各种各样的结构来解决这些问题。其中有一种数据结构，也就是我们今天要提到的字典(map/dict)，它在各方面效率做到了很好的平衡，它的经典实现方式是hash table，也有很多其它实现方式，但不管是怎样实现的，映射在内存层面仍然是数组，那么它是怎样实现的呢？
首先，我们不考虑value，仅看key是怎么映射到数组上的。数组通过下标数字访问，不管key是什么类型，我们都需要把它通过哈希函数转换为一个数字，若得到的数字很大超过了数组的长度，我们就可以通过取模(n%len)的方式来得到它在数组中的位置。所以任何一个可哈希的Key我们都能把它映射到数组上的某个位置，那么我们就可以把key-value打包为一个struct放在数组中某个位置，解决了高效的查找和编辑的问题。
接下来的问题就是哈希碰撞了。当两个key哈希并取模后的结果是相同的数字时，有一个简单的处理方式就是用链表链起来，即链表法，把一个横向的大的数组转化为了多个纵向的小的链表，Go采用的这种方式。另外一种方法就是若发现冲突，则把新的key加上一个magic_number计算得出一个新的位置，横向的填充到这个空位，称为开放寻址法，Python采用这种方式。
链表法的问题就在于链表的访问效率差，如何优化？当CPU去读取数据时，它会基于空间局部性原则将附近的数据从内存读入L3，然后是L2、L1。那么我们基于这个原则，应当把链表转换为数组，把原有的一个个的item放入一个桶中:
把每8(或8的倍数)个item当做一个桶，一个桶链接另一个桶。当我们需要根据某个查询条件查询数据的时候，我们可以把整个桶拿出来遍历查找，很可能整个桶是被L1或者L3缓存过的，这个访问效率就可能比在内存中去读取快上百倍。
那么针对这个桶是否还有优化空间呢？我们发现遍历的时候是去判断它的key是否相等，并不需要知道它的value。按照当前这种结构value就占用了缓存器的空间:
我们应该尽可能的缓存更多的keys，于是可以把桶分为上下两个部分:
那么还能进一步优化吗？我们发现keys的数据类型不知道，如果是个整数倒还很容易和查询条件做比较，但若是个字符串，两个字符串的比较效率是非常低的。针对这种情况，我们可以再做一层访问拦截:
这层数组放入keys的哈希值，只有当某个位置的哈希值和查询条件匹配时，我们才会去进一步比对keys数组中对应位置的key。这样我们就通过一个整数型数组拦截掉了很多的预判。甚至这个整数数组也无需使用int64，我们只取hashcode的高位构成一个int8类型，[8]int8形成一个64位的数组正好能被一个寄存器存下。
另外这层数组像一个位图，还能用来判断这个桶中还有没有空位，插入数据时先看数组中是否有空位就可以相应的在keys和values中找到空位，删除数据时也不会进行收缩，只是在相应的位置上做标记。
现在，我们经过一层层的优化，字典变成了这个样子:
只要哈希算法分布的很平均，那么基础数组越长，桶的链表就越短，访问效率也越高，这就涉及到一个扩容的问题。随着数据的插入，键值对的总个数和基础数组的长度有一个比例，当这个比例达到一个阈值，就会触发扩容操作。扩容时我们不能直接新建个基础数组，然后把原数组数据一次性搬过去，这种方式会导致某次操作的时间过长使应用卡死。而应该在触发时，设定一个标志，之后对这个字典的每次查询、修改、插入、删除都先去检查这个标志，若标志为真且本次操作的数据在旧字典中，则将它及附近的一段数据都迁移至新字典，这叫随机迁移。同时，为防止每次操作都发生在新字典中，其内部还有个计数器，让其迁移时能够从旧字典的头部再顺序迁移一部分数据，也就是顺序迁移。这样就能保证所有的数据都被迁移过去，迁移完成后，旧字典整个被释放掉。
当删除字典元素时，对于Go这种关注性能的语言，字典的内存不会被压缩，可能会造成内存浪费。如果有大量删除元素的情况，只能新建一个字典，把旧字典的数据手工搬过去，让垃圾回收器回收旧字典。基于这个原因，我们在桶中应该去存储keys和values的内容而不是它们的指针。因为key和value的生命周期是和整个map相同的，不存指针也就意味着减轻了垃圾回收期的压力，原本需要检查回收1(map)&#43;n(keys)&#43;n(values)个对象变为了只需检查1个map对象。所以Go中做了如下设定，如果key和value的长度小于128字节，同时key和value本身不是指针，那么它们会被嵌入到字典内部。
通过以上，我们了解到任何一个看似简单的东西背后可能都隐藏了复杂的设计。"><meta property="og:title" content="字典" />
<meta property="og:description" content="" />
<meta property="og:type" content="website" />
<meta property="og:url" content="/docs/go/map/" />

<title>字典 | Home</title>
<link rel="icon" href="/favicon.png" type="image/x-icon">
<link rel="stylesheet" href="/book.min.63eb88daa545365405ecdbb21033286a325c60a36cfa6d22d21e7c3bc9286941.css" integrity="sha256-Y&#43;uI2qVFNlQF7NuyEDMoajJcYKNs&#43;m0i0h58O8koaUE=">
<script defer src="/cn.search.min.8d2462c3b745732864d843e8e2e7782a2ec838ca90fb94676baa461536bdae11.js" integrity="sha256-jSRiw7dFcyhk2EPo4ud4Ki7IOMqQ&#43;5Rna6pGFTa9rhE="></script>
<link rel="alternate" type="application/rss+xml" href="/docs/go/map/index.xml" title="Home" />
<!--
Made with Book Theme
https://github.com/alex-shpak/hugo-book
-->

  
</head>

<body>
  <input type="checkbox" class="hidden" id="menu-control" />
  <main class="container flex">
    <aside class="book-menu">
      
  <nav>
<h2 class="book-brand">
  <a href="/"><img src="/logo.png" alt="Logo" /><span>Home</span>
  </a>
</h2>


<div class="book-search">
  <input type="text" id="book-search-input" placeholder="搜索" aria-label="搜索" maxlength="64" data-hotkeys="s/" />
  <div class="book-search-spinner spinner hidden"></div>
  <ul id="book-search-results"></ul>
</div>











  <ul>
<li><strong>计算机基础</strong>
<ul>
<li><a href="/docs/sicp/hardware/">硬件</a></li>
<li><a href="/docs/sicp/software/">软件</a></li>
<li><a href="/docs/sicp/program/">程序</a></li>
<li><a href="/docs/sicp/asm/">汇编</a></li>
</ul>
</li>
<li><strong>GO语言</strong>
<ul>
<li><a href="/docs/go/map/"class=active>字典</a></li>
<li><a href="/docs/go/closure/">闭包</a></li>
<li><a href="/docs/go/defer/">延迟调用</a></li>
<li><a href="/docs/go/goroutine/">并发调度</a></li>
<li><a href="/docs/go/alloc/">内存分配</a></li>
<li><a href="/docs/go/gc/">垃圾回收</a></li>
<li><a href="/docs/go/lock/">锁</a></li>
</ul>
</li>
<li><strong>Python语言</strong>
<ul>
<li><a href="/docs/python/memory/">内存管理</a></li>
<li><a href="/docs/python/interpreter/">解释器</a></li>
<li><a href="/docs/python/tools/">技巧工具</a></li>
</ul>
</li>
<li><strong>Mysql</strong>
<ul>
<li><a href="/docs/mysql/query/">查询</a></li>
<li><a href="/docs/mysql/theory/">原理</a></li>
</ul>
</li>
<li><strong>其他</strong>
<ul>
<li><a href="/docs/other/git/">git</a></li>
<li><a href="/docs/other/docker/">docker</a></li>
<li><a href="/docs/other/raft/">raft</a></li>
<li><a href="/docs/other/shell/">shell</a></li>
<li><a href="/docs/other/oop/">面向对象</a></li>
<li><a href="/docs/other/protocol/">网络协议</a></li>
<li><a href="/docs/other/tools/">系统工具</a></li>
</ul>
</li>
</ul>










</nav>




  <script>(function(){var menu=document.querySelector("aside.book-menu nav");addEventListener("beforeunload",function(event){localStorage.setItem("menu.scrollTop",menu.scrollTop);});menu.scrollTop=localStorage.getItem("menu.scrollTop");})();</script>


 
    </aside>

    <div class="book-page">
      <header class="book-header">
        
  <div class="flex align-center justify-between">
  <label for="menu-control">
    <img src="/svg/menu.svg" class="book-icon" alt="Menu" />
  </label>

  <strong>字典</strong>

  <label for="toc-control">
    <img src="/svg/toc.svg" class="book-icon" alt="Table of Contents" />
  </label>
</div>


  
 
      </header>

      
      
  <article class="markdown"><h1 id="字典">字典</h1>
<p>现代编程语言，例如Python和Go中都有字典，其作为一种常见数据结构使用频率非常高。一般作为内置类型，解释器或者编译器都会对其特别的照顾，做相当多的优化，它的设计也需要在通用和性能上找到平衡，当然也是我们非常好的学习案例。</p>
<p>要存储一批数据，我们最先想到的就是用数组，因为它对所有的存储器亲和性是最好的，内存可以看成是一个大的字节数组，CPU cache line也是一个64字节的数组。但数组有个问题，即索引效率低，我们往往是通过排序然后进行二分查找来提高索引的效率。可是如果我们的数据需要频繁的编辑(插入、删除、修改)时，这种排序就可能造成我们需要频繁的对其中的局部进行重排，这时候延伸出了大小堆、树堆等各种各样的结构来解决这些问题。其中有一种数据结构，也就是我们今天要提到的字典(map/dict)，它在各方面效率做到了很好的平衡，它的经典实现方式是hash table，也有很多其它实现方式，但不管是怎样实现的，映射在内存层面仍然是数组，那么它是怎样实现的呢？</p>
<p>首先，我们不考虑value，仅看key是怎么映射到数组上的。数组通过下标数字访问，不管key是什么类型，我们都需要把它通过哈希函数转换为一个数字，若得到的数字很大超过了数组的长度，我们就可以通过取模(n%len)的方式来得到它在数组中的位置。所以任何一个可哈希的Key我们都能把它映射到数组上的某个位置，那么我们就可以把key-value打包为一个struct放在数组中某个位置，解决了高效的查找和编辑的问题。</p>
<p>接下来的问题就是哈希碰撞了。当两个key哈希并取模后的结果是相同的数字时，有一个简单的处理方式就是用链表链起来，即链表法，把一个横向的大的数组转化为了多个纵向的小的链表，Go采用的这种方式。另外一种方法就是若发现冲突，则把新的key加上一个magic_number计算得出一个新的位置，横向的填充到这个空位，称为开放寻址法，Python采用这种方式。</p>
<p>链表法的问题就在于链表的访问效率差，如何优化？当CPU去读取数据时，它会基于空间局部性原则将附近的数据从内存读入L3，然后是L2、L1。那么我们基于这个原则，应当把链表转换为数组，把原有的一个个的item放入一个桶中:</p>
<p><img src="images/1.jpg" alt="" /></p>
<p>把每8(或8的倍数)个item当做一个桶，一个桶链接另一个桶。当我们需要根据某个查询条件查询数据的时候，我们可以把整个桶拿出来遍历查找，很可能整个桶是被L1或者L3缓存过的，这个访问效率就可能比在内存中去读取快上百倍。</p>
<p>那么针对这个桶是否还有优化空间呢？我们发现遍历的时候是去判断它的key是否相等，并不需要知道它的value。按照当前这种结构value就占用了缓存器的空间:</p>
<p><img src="images/2.jpg" alt="" /></p>
<p>我们应该尽可能的缓存更多的keys，于是可以把桶分为上下两个部分:</p>
<p><img src="images/3.jpg" alt="" /></p>
<p>那么还能进一步优化吗？我们发现keys的数据类型不知道，如果是个整数倒还很容易和查询条件做比较，但若是个字符串，两个字符串的比较效率是非常低的。针对这种情况，我们可以再做一层访问拦截:</p>
<p><img src="images/4.jpg" alt="" /></p>
<p>这层数组放入keys的哈希值，只有当某个位置的哈希值和查询条件匹配时，我们才会去进一步比对keys数组中对应位置的key。这样我们就通过一个整数型数组拦截掉了很多的预判。甚至这个整数数组也无需使用int64，我们只取hashcode的高位构成一个int8类型，[8]int8形成一个64位的数组正好能被一个寄存器存下。</p>
<p>另外这层数组像一个位图，还能用来判断这个桶中还有没有空位，插入数据时先看数组中是否有空位就可以相应的在keys和values中找到空位，删除数据时也不会进行收缩，只是在相应的位置上做标记。</p>
<p>现在，我们经过一层层的优化，字典变成了这个样子:</p>
<p><img src="images/5.jpg" alt="" /></p>
<p>只要哈希算法分布的很平均，那么基础数组越长，桶的链表就越短，访问效率也越高，这就涉及到一个扩容的问题。随着数据的插入，键值对的总个数和基础数组的长度有一个比例，当这个比例达到一个阈值，就会触发扩容操作。扩容时我们不能直接新建个基础数组，然后把原数组数据一次性搬过去，这种方式会导致某次操作的时间过长使应用卡死。而应该在触发时，设定一个标志，之后对这个字典的每次查询、修改、插入、删除都先去检查这个标志，若标志为真且本次操作的数据在旧字典中，则将它及附近的一段数据都迁移至新字典，这叫<strong>随机迁移</strong>。同时，为防止每次操作都发生在新字典中，其内部还有个计数器，让其迁移时能够从旧字典的头部再顺序迁移一部分数据，也就是<strong>顺序迁移</strong>。这样就能保证所有的数据都被迁移过去，迁移完成后，旧字典整个被释放掉。</p>
<p>当删除字典元素时，对于Go这种关注性能的语言，字典的内存不会被压缩，可能会造成内存浪费。如果有大量删除元素的情况，只能新建一个字典，把旧字典的数据手工搬过去，让垃圾回收器回收旧字典。基于这个原因，我们在桶中应该去存储keys和values的内容而不是它们的指针。因为key和value的生命周期是和整个map相同的，不存指针也就意味着减轻了垃圾回收期的压力，原本需要检查回收1(map)+n(keys)+n(values)个对象变为了只需检查1个map对象。所以Go中做了如下设定，如果key和value的长度小于128字节，同时key和value本身不是指针，那么它们会被嵌入到字典内部。</p>
<p>通过以上，我们了解到任何一个看似简单的东西背后可能都隐藏了复杂的设计。</p>
</article>
 
      

      <footer class="book-footer">
        
  <div class="flex justify-between">



  <div>
    
    <a class="flex align-center" href="https://github.com/hjlarry/hjlarry.github.io/commit/f8b0a0ee517ea9997b10393cb3ff6c0550d75328" title='最后修改者 hjlarry | December 23, 2019' target="_blank" rel="noopener">
      <img src="/svg/calendar.svg" class="book-icon" alt="Calendar" />
      <span>December 23, 2019</span>
    </a>
  </div>



  <div>
    <a class="flex align-center" href="https://github.com/hjlarry/hjlarry.github.io/edit/master/content/docs/go/map/_index.md" target="_blank" rel="noopener">
      <img src="/svg/edit.svg" class="book-icon" alt="Edit" />
      <span>编辑本页</span>
    </a>
  </div>

</div>

 
        <br>
<div style="text-align: center;font-size:xx-small;">
    Powered by <a href="https://gohugo.io" target="_blank">Hugo</a> | Theme by <a
        href="https://github.com/alex-shpak/hugo-book" target="_blank">hugo-book</a>
</div>
      </footer>

      
  
 

      <label for="menu-control" class="hidden book-menu-overlay"></label>
    </div>

    
  </main>

  
</body>

</html>












